//==============================
// Function parser v2.2 by Warp
//==============================

// Comment out the following line if your compiler supports the (non-standard)
// asinh, acosh and atanh functions and you want them to be supported. If
// you are not sure, just leave it (those function will then not be supported).


// Uncomment the following line to disable the eval() function if it could
// be too dangerous in the target application:
//#define DISABLE_EVAL

#include "StdAfx.h"
#include <pgl/algotools/fparser.h>

#define FCN_PARSER_NO_ASINH

namespace fcnparser
{
	LPCTSTR CFunctionParser::m_FuncNames[]=
    {
			 _T("abs"),_T("exp"),_T("ceil"),_T("floor"),_T("log"),_T("sqrt"),_T("int"),
			_T("sinh"),_T("cosh"),_T("tanh"),_T("sin"),_T("cos"),_T("tan"),
			_T("asin"),_T("acos"),_T("atan"),
			_T("min"), _T("max"), _T("if"),
			_T("eval"),
			0
    };
    const unsigned CFunctionParser::m_FuncParams[]=
    {
        1, 1, 1, 1, 1, 1, 1,
			1, 1, 1, 1, 1, 1,
			1, 1, 1,
			2, 2, 0,
			0
    };

		
	//---------------------------------------------------------------------------
	// Constructors and destructors
	//---------------------------------------------------------------------------
	//===========================================================================
	CFunctionParser::CFunctionParser():
    m_iParseErrorType(-1), m_iEvalErrorType(0),m_iVarAmount(0)
	{
		m_mVariables.clear();
		for(unsigned fInd = 0; m_FuncNames[fInd]; ++fInd)	
		{
			m_mFunctions[m_FuncNames[fInd]] = FuncDefinition(cAbs+fInd, m_FuncParams[fInd]);
		}
	}
	
	// Copy constructor (only for private use)
	CFunctionParser::CFunctionParser(const CFunctionParser& cpy):
		m_iVarAmount(cpy.m_iVarAmount),
		m_iParseErrorType(cpy.m_iParseErrorType),
		m_iEvalErrorType(cpy.m_iEvalErrorType),
		Comp(cpy.Comp),
		m_sVars(cpy.m_sVars),
		m_sFunction(cpy.m_sFunction),
		m_mFunctions(cpy.m_mFunctions),
		m_mVariables(cpy.m_mVariables)
	{
	}
	
	CFunctionParser::~CFunctionParser() {}
	
	SComp::SComp():
    ByteCode(0), ByteCodeSize(0),
		Immed(0), ImmedSize(0),
		Stack(0), StackSize(0),
		thisIsACopy(false)
	{}
	
	SComp::~SComp()
	{
		if(!thisIsACopy && ByteCode) 
		{ 
			delete[] ByteCode; 
			ByteCode=NULL; 
		}
		if(!thisIsACopy && Immed) 
		{ 
			delete[] Immed; 
			Immed=NULL; 
		}
		if(Stack) 
		{ 
			delete[] Stack; 
			Stack=NULL; 
		}
	}
	
	
	//---------------------------------------------------------------------------
	// Function parsing
	//---------------------------------------------------------------------------
	//===========================================================================
	
    // Return index to original std::_tstring when the index is to the function
    // with no whitespaces
    inline int RealIndexPos(const std::_tstring& s,int Pos)
    {
        int i, Ind=0;
        for(i=0; i<Pos; i++,Ind++)
            while(s[Ind]==' ') Ind++;
			while(s[Ind]==' ') Ind++;
			return Ind;
    }
	
    // Parse variables
    bool CFunctionParser::ParseVars(const std::_tstring& Vars)
    {
        unsigned varNumber = VarBegin;
        unsigned ind1 = 0, ind2;
		
		m_mVariables.clear();
        while(ind1 < Vars.size())
        {
            for(ind2=ind1; ind2<Vars.size() && Vars[ind2]!=','; ++ind2)
			{
                if(!_istalpha(Vars[ind2])) 
				{
					return false;
				}
			}
			if(ind2 == ind1) 
			{
				return false;
			}
				
			const std::_tstring varName = Vars.substr(ind1, ind2-ind1);
			StringMap_t::const_iterator iter = m_mVariables.find( varName );
			if(iter != m_mVariables.end()) 
			{
				return false;
			}
			m_mVariables.insert( StringMap_t::value_type(varName,varNumber++) );
				
			ind1 = ind2+1;
        }
        return true;
    }
	
	// Main parsing function
	int CFunctionParser::Parse(LPCTSTR szFunction, LPCTSTR szVars)
	{
		m_mVariables.clear();
		if (!_tcslen(szFunction) || !_tcslen(szVars))
		{
			m_iParseErrorType = 7;
			TRACE(_T("Error: %s"), GetEvalErrorMsg(m_iParseErrorType));
			
			return m_sFunction.size();
		}
		TRACE(_T("CFunctionParser: Start parsing:%s with %s ...\n"), szFunction, szVars);
		m_sFunction=szFunction;
		m_sVars=szVars;

		if(!ParseVars(m_sVars))
		{
			m_iParseErrorType = 7;
			TRACE(_T("Error: %s"), GetEvalErrorMsg(m_iParseErrorType));
			
			return m_sFunction.size();
		}
		m_iVarAmount = m_mVariables.size(); // this is for Eval()
		
		std::_tstring tmp;
		tmp.reserve(m_sFunction.size());
		for(unsigned i=0; i<m_sFunction.size(); ++i)
		{
			if(! isspace(m_sFunction[i]) )
			{
				tmp += m_sFunction[i];
			}
		}

		LPCTSTR Func = tmp.c_str();
			
		m_iParseErrorType = -1;
			
		int Result = CheckSyntax(Func);
		if(Result>=0)
		{
			return RealIndexPos(m_sFunction, Result);
		}
			
		if(!Compile(Func)) 
			return m_sFunction.size();
			
		m_mVariables.clear();
			
		m_iParseErrorType = -1;
		TRACE(_T("Success\n"));
			
		return -1;
	}

	
	//---------------------------------------------------------------------------
	// Check function std::_tstring syntax
	// ----------------------------
	int CFunctionParser::CheckSyntax(LPCTSTR Function)
	{
		int Ind=0,ParenthCnt=0,c;
		LPTSTR Ptr;
		
		while(true)
		{
			c=Function[Ind];
			
			// Check for valid operand (must appear)
			
			// Check for leading -
			if(c=='-') c=Function[++Ind];
			if(c==0) 
			{ 
				m_iParseErrorType=9; 
				return Ind; 
			}
			
			// Check for math function
			FuncMap_t::const_iterator fIter = FindFunction( &Function[Ind] );
			if(fIter != m_mFunctions.end())
			{
				Ind += fIter->first.size();
				c = Function[Ind];
				if(c!='(') 
				{ 
					m_iParseErrorType=10; 
					return Ind; 
				}
			}
			
			// Check for opening parenthesis
			if(c=='(') 
			{ 
				ParenthCnt++; Ind++; continue; 
			}
			
			// Check for number
			if(isdigit(c) || (c=='.' && isdigit(Function[Ind+1])))
			{
				_tcstod(&Function[Ind], &Ptr);
				Ind += int(Ptr-&Function[Ind]);
				c = Function[Ind];
			}
			else
			{ // Check for variable
				StringMap_t::const_iterator vIter = FindVariable(&Function[Ind]);
				if(vIter == m_mVariables.end()) 
				{ 
					m_iParseErrorType=11; 
					return Ind; 
				}
				Ind += vIter->first.size();
				c = Function[Ind];
			}
			
			// Check for closing parenthesis
			while(c==')')
			{
				ParenthCnt--;
				if(ParenthCnt<0) 
				{ 
					m_iParseErrorType=1; return Ind; 
				}
				if(Function[Ind-1]=='(') 
				{ 
					m_iParseErrorType=3; return Ind; 
				}
				c=Function[++Ind];
			}
			
			// If we get here, we have a legal operand and now a legal operator or
			// end of std::_tstring must follow
			
			// Check for EOS
			if(c==0) break; // The only way to end the checking loop without error
			// Check for operator
			if(!IsOperator(c)) 
			{ 
				m_iParseErrorType=4; return Ind; 
			}
			
			// If we get here, we have an operand and an operator; the next loop will
			// check for another operand (must appear)
			++Ind;
		} // while
		
		// Check that all opened parentheses are also closed
		if(ParenthCnt>0) 
		{ 
			m_iParseErrorType=2; return Ind; 
		}
		
		// The std::_tstring is ok
		m_iParseErrorType=-1;
		return -1;
	}
	
	// Compile function std::_tstring to bytecode
	// -----------------------------------
	bool CFunctionParser::Compile(LPCTSTR Function)
	{
		if(Comp.ByteCode) { delete[] Comp.ByteCode; Comp.ByteCode=0; }
		if(Comp.Immed) { delete[] Comp.Immed; Comp.Immed=0; }
		if(Comp.Stack) { delete[] Comp.Stack; Comp.Stack=0; }
		
		// Compile to nowhere to get the size of the bytecode
		Comp.ByteCodeSize=Comp.ImmedSize=Comp.StackSize=Comp.StackPtr=0;
		CompileExpression(Function, 0);
		if(m_iParseErrorType >= 0) return false;
		
		try
		{
			if(Comp.ByteCodeSize)
				Comp.ByteCode = new unsigned[Comp.ByteCodeSize];
			if(Comp.ImmedSize)
				Comp.Immed = new double[Comp.ImmedSize];
			if(Comp.StackSize)
				Comp.Stack = new double[Comp.StackSize];
		}
		catch(std::bad_alloc)
		{
			m_iParseErrorType=5; return false;
			// Already allocated memory blocks are freed in the destructor or when
			// Parse() is called again, so no need to free them here
		}
		
		// Compile
		Comp.ByteCodeSize=Comp.ImmedSize=Comp.StackSize=Comp.StackPtr=0;
		CompileExpression(Function, 0);
		
		return m_iParseErrorType < 0;
	}
	
	inline void CFunctionParser::AddCompiledByte(unsigned c)
	{
		if(Comp.ByteCode)
			Comp.ByteCode[Comp.ByteCodeSize] = c;
		++Comp.ByteCodeSize;
	}
	
	// Compile if()
	int CFunctionParser::CompileIf(LPCTSTR F, int ind)
	{
		int ind2 = CompileExpression(F, ind, true); // condition
		if(F[ind2] != ',') { m_iParseErrorType=8; return ind2; }
		AddCompiledByte(cIf);
		unsigned curByteCodeSize = Comp.ByteCodeSize;
		AddCompiledByte(0); // Jump index; to be set later
		AddCompiledByte(0); // Immed jump index; to be set later
		
		--Comp.StackPtr;
		
		ind2 = CompileExpression(F, ind2+1, true); // then
		if(F[ind2] != ',') { m_iParseErrorType=8; return ind2; }
		AddCompiledByte(cJump);
		unsigned curByteCodeSize2 = Comp.ByteCodeSize;
		unsigned curImmedSize2 = Comp.ImmedSize;
		AddCompiledByte(0); // Jump index; to be set later
		AddCompiledByte(0); // Immed jump index; to be set later
		
		--Comp.StackPtr;
		
		ind2 = CompileExpression(F, ind2+1, true); // else
		if(F[ind2] != ')') { m_iParseErrorType=8; return ind2; }
		
		if(Comp.ByteCode) // Set jump indices
		{
			Comp.ByteCode[curByteCodeSize] = curByteCodeSize2+1;
			Comp.ByteCode[curByteCodeSize+1] = curImmedSize2;
			Comp.ByteCode[curByteCodeSize2] = Comp.ByteCodeSize-1;
			Comp.ByteCode[curByteCodeSize2+1] = Comp.ImmedSize;
		}
		
		return ind2+1;
	}
	
	// Compiles element
	int CFunctionParser::CompileElement(LPCTSTR F, int ind)
	{
		TCHAR c = F[ind];
		
		if(c == '(')
		{
			return CompileExpression(F, ind+1) + 1;
		}
		else if(c == '-')
		{
			int ind2 = CompileElement(F, ind+1);
			AddCompiledByte(cNeg);
			return ind2;
		}
		
		if(_istdigit(c) || c=='.') // Number
		{
			LPCTSTR startPtr = &F[ind];
			LPTSTR endPtr;
			double val = _tcstod(startPtr, &endPtr);
			if(Comp.Immed)
				Comp.Immed[Comp.ImmedSize] = val;
			++Comp.ImmedSize;
			AddCompiledByte(cImmed);
			++Comp.StackPtr; if(Comp.StackPtr>Comp.StackSize) Comp.StackSize++;
			return ind+(endPtr-startPtr);
		}
		
		if(_istalpha(c)) // Function or variable
		{
			int ind2 = ind+1;
			while(_istalpha(F[ind2])) ++ind2;
			std::_tstring name(F+ind, ind2-ind);
			
			FuncMap_t::const_iterator fIter = m_mFunctions.find(name);
			if(fIter != m_mFunctions.end()) // is function
			{
				if(fIter->first.compare(_T("if")) == 0) // "if" is a special case
				{
					return CompileIf(F, ind2+1);
				}
				
				unsigned curStackPtr = Comp.StackPtr;
				ind2 = CompileExpression(F, ind2+1);
				
#ifndef DISABLE_EVAL
				unsigned requiredParams =
					(fIter->first.compare(_T("eval")) == 0) ? m_mVariables.size() : fIter->second.params;
#else
				unsigned requiredParams = fIter->second.params;
#endif
				if(Comp.StackPtr != curStackPtr+requiredParams)
				{ m_iParseErrorType=8; return ind; }
				
				AddCompiledByte(fIter->second.opcode);
				Comp.StackPtr -= fIter->second.params - 1;
				return ind2+1;
			}
			
			StringMap_t::const_iterator vIter = m_mVariables.find(name);
			if(vIter != m_mVariables.end()) // is variable
			{
				AddCompiledByte(vIter->second);
				++Comp.StackPtr; 

				if(Comp.StackPtr>Comp.StackSize) 
					Comp.StackSize++;

				return ind + vIter->first.size();
			}
		}
		
		m_iParseErrorType = 6;
		return ind;
	}
	
	// Compiles '^'
	int CFunctionParser::CompilePow(LPCTSTR F, int ind)
	{
		int ind2 = CompileElement(F, ind);
		
		while(F[ind2] == '^')
		{
			ind2 = CompileElement(F, ind2+1);
			AddCompiledByte(cPow);
			--Comp.StackPtr;
		}
		
		return ind2;
	}
	
	// Compiles '*', '/' and '%'
	int CFunctionParser::CompileMult(LPCTSTR F, int ind)
	{
		int ind2 = CompilePow(F, ind);
		TCHAR op;
		
		while((op = F[ind2]) == '*' || op == '/' || op == '%')
		{
			ind2 = CompilePow(F, ind2+1);
			switch(op)
			{
			case '*': AddCompiledByte(cMul); break;
			case '/': AddCompiledByte(cDiv); break;
			case '%': AddCompiledByte(cMod); break;
			}
			--Comp.StackPtr;
		}
		
		return ind2;
	}
	
	// Compiles '+' and '-'
	int CFunctionParser::CompileAddition(LPCTSTR F, int ind)
	{
		int ind2 = CompileMult(F, ind);
		TCHAR op;
		
		while((op = F[ind2]) == '+' || op == '-')
		{
			ind2 = CompileMult(F, ind2+1);
			AddCompiledByte(op=='+' ? cAdd : cSub);
			--Comp.StackPtr;
		}
		
		return ind2;
	}
	
	// Compiles '=', '<' and '>'
	int CFunctionParser::CompileComparison(LPCTSTR F, int ind)
	{
		int ind2 = CompileAddition(F, ind);
		TCHAR op;
		
		while((op = F[ind2]) == '=' || op == '<' || op == '>')
		{
			ind2 = CompileAddition(F, ind2+1);
			switch(op)
			{
			case '=': AddCompiledByte(cEqual); break;
			case '<': AddCompiledByte(cLess); break;
			case '>': AddCompiledByte(cGreater); break;
			}
			--Comp.StackPtr;
		}
		
		return ind2;
	}
	
	// Compiles '&'
	int CFunctionParser::CompileAnd(LPCTSTR F, int ind)
	{
		int ind2 = CompileComparison(F, ind);
		
		while(F[ind2] == '&')
		{
			ind2 = CompileComparison(F, ind2+1);
			AddCompiledByte(cAnd);
			--Comp.StackPtr;
		}
		
		return ind2;
	}
	

	// Compiles '|'
	int CFunctionParser::CompileOr(LPCTSTR F, int ind)
	{
		int ind2 = CompileAnd(F, ind);
		
		while(F[ind2] == '|')
		{
			ind2 = CompileAnd(F, ind2+1);
			AddCompiledByte(cOr);
			--Comp.StackPtr;
		}
		
		return ind2;
	}
	
	// Compiles ','
	int CFunctionParser::CompileExpression(LPCTSTR F, int ind, bool stopAtComma)
	{
		int ind2 = CompileOr(F, ind);
		
		if(stopAtComma) return ind2;
		
		while(F[ind2] == ',')
		{
			ind2 = CompileOr(F, ind2+1);
		}
		
		return ind2;
	}
	
	
	// Return parse error message
	// --------------------------
	LPCTSTR CFunctionParser::GetParseErrorMsg(void) const
	{
		switch(m_iParseErrorType)
		{
		case 0: return _T("Syntax error");                             // 0
		case 1: return _T("Mismatched parenthesis");                   // 1
		case 2: return _T("Missing ')'");                              // 2
		case 3: return _T("Empty parentheses");                       // 3
		case 4: return _T("Syntax error. Operator expected");          // 4
		case 5: return _T("Not enough memory");                        // 5
		case 6: return _T("An unexpected error ocurred. Please make a full bug report to warp@iki.fi");                           // 6
		case 7: return _T("Syntax error in parameter 'Vars' given to CFunctionParser::Parse()");                  // 7
		case 8: return _T("Illegal number of parameters to function");  // 8
		case 9: return _T("Unexpected end of string in function. Is the function strin empty?");
		case 10: return _T("Missing ( after function.");
		case 11: return _T("Contains a string that is not a variable, neither a function");
		default:
			return _T("Parse successfull");
		};
	}
	
    LPCTSTR CFunctionParser::GetEvalErrorMsg(unsigned iEvalErrorType)
	{
		switch(iEvalErrorType)
		{
        case 1: return _T("Division by zero");
        case 2: return _T("Sqrt error (sqrt of a negative value)");
        case 3: return _T("Log error (logarithm of a negative value)");
        case 4: return _T("Trigonometric error (asin or acos of illegal value)");
        case 5: return _T("Not the right number of parameters");
		default:
			return _T("Eval successfull");
		};
	}

	//---------------------------------------------------------------------------
	// Function evaluation
	//---------------------------------------------------------------------------
	//===========================================================================
    inline int doubleToInt(double d)
    {
        return d<0 ? -int((-d)+.5) : int(d+.5);
    }
	
    inline double Min(double d1, double d2)
    {
        return d1<d2 ? d1 : d2;
    }
    inline double Max(double d1, double d2)
    {
        return d1>d2 ? d1 : d2;
    }
	
	
	double CFunctionParser::Eval(const double* Vars) const
	{
		unsigned IP, DP=0;
		int SP=-1;
		
		if (m_iVarAmount < sizeof(Vars)/sizeof(Vars[0]))
		{
			throw GetEvalErrorMsg(5);
		}

		if (!Comp.ByteCodeSize)
			return 0;

		for(IP=0; IP<Comp.ByteCodeSize; IP++)
		{
			switch(Comp.ByteCode[IP])
			{
			case cImmed: Comp.Stack[++SP]=Comp.Immed[DP++]; break;
				
			case  cJump: DP = Comp.ByteCode[IP+2];
				IP = Comp.ByteCode[IP+1];
				break;
				
			case   cNeg: Comp.Stack[SP]=-Comp.Stack[SP]; break;
			case   cAdd: Comp.Stack[SP-1]+=Comp.Stack[SP]; SP--; break;
			case   cSub: Comp.Stack[SP-1]-=Comp.Stack[SP]; SP--; break;
			case   cMul: Comp.Stack[SP-1]*=Comp.Stack[SP]; SP--; break;
			case   cDiv: Comp.Stack[SP-1]=Comp.Stack[SP-1]/Comp.Stack[SP]; SP--; break;
			case   cMod: if(Comp.Stack[SP]==0) { throw GetEvalErrorMsg(1); }
				Comp.Stack[SP-1]=fmod(Comp.Stack[SP-1],Comp.Stack[SP]);
				SP--; break;
			case   cPow: Comp.Stack[SP-1]=pow(Comp.Stack[SP-1],Comp.Stack[SP]);
				SP--; break;
				
			case cEqual: Comp.Stack[SP-1] = (Comp.Stack[SP-1]==Comp.Stack[SP]);
				SP--; break;
			case  cLess: Comp.Stack[SP-1] = (Comp.Stack[SP-1]<Comp.Stack[SP]);
				SP--; break;
			case cGreater: Comp.Stack[SP-1] = (Comp.Stack[SP-1]>Comp.Stack[SP]);
				SP--; break;
			case   cAnd: Comp.Stack[SP-1] =
							 (doubleToInt(Comp.Stack[SP-1]) &&
							 doubleToInt(Comp.Stack[SP]));
				SP--; break;
			case    cOr: Comp.Stack[SP-1] =
							 (doubleToInt(Comp.Stack[SP-1]) ||
							 doubleToInt(Comp.Stack[SP]));
				SP--; break;
				
			case   cAbs: Comp.Stack[SP]=fabs(Comp.Stack[SP]); break;
			case   cExp: Comp.Stack[SP]=exp(Comp.Stack[SP]); break;
			case  cCeil: Comp.Stack[SP]=ceil(Comp.Stack[SP]); break;
			case cFloor: Comp.Stack[SP]=floor(Comp.Stack[SP]); break;
			case   cLog: if(Comp.Stack[SP]<=0) { throw GetEvalErrorMsg(3); }
				Comp.Stack[SP]=log(Comp.Stack[SP]); break;
			case  cSqrt: if(Comp.Stack[SP]<0) { throw GetEvalErrorMsg(2); }
				Comp.Stack[SP]=sqrt(Comp.Stack[SP]); break;
			case   cInt: Comp.Stack[SP]=doubleToInt(Comp.Stack[SP]); break;
			case  cSinh: Comp.Stack[SP]=sinh(Comp.Stack[SP]); break;
			case  cCosh: Comp.Stack[SP]=cosh(Comp.Stack[SP]); break;
			case  cTanh: Comp.Stack[SP]=tanh(Comp.Stack[SP]); break;
			case   cSin: Comp.Stack[SP]=sin(Comp.Stack[SP]); break;
			case   cCos: Comp.Stack[SP]=cos(Comp.Stack[SP]); break;
			case   cTan: Comp.Stack[SP]=tan(Comp.Stack[SP]); break;
#ifndef FCN_PARSER_NO_ASINH
			case cAsinh: Comp.Stack[SP]=asinh(Comp.Stack[SP]); break;
			case cAcosh: Comp.Stack[SP]=acosh(Comp.Stack[SP]); break;
			case cAtanh: Comp.Stack[SP]=atanh(Comp.Stack[SP]); break;
#endif
			case  cAsin: if(Comp.Stack[SP]<-1 || Comp.Stack[SP]>1)
						 { throw GetEvalErrorMsg(4); }
				Comp.Stack[SP]=asin(Comp.Stack[SP]); break;
			case  cAcos: if(Comp.Stack[SP]<-1 || Comp.Stack[SP]>1)
						 { throw GetEvalErrorMsg(4); }
				Comp.Stack[SP]=acos(Comp.Stack[SP]); break;
			case  cAtan: Comp.Stack[SP]=atan(Comp.Stack[SP]); break;
				
			case   cMin: Comp.Stack[SP-1]=Min(Comp.Stack[SP-1],Comp.Stack[SP]);
				SP--; break;
			case   cMax: Comp.Stack[SP-1]=Max(Comp.Stack[SP-1],Comp.Stack[SP]);
				SP--; break;
			case    cIf:
				{
					unsigned jumpAddr = Comp.ByteCode[++IP];
					unsigned immedAddr = Comp.ByteCode[++IP];
					if(doubleToInt(Comp.Stack[SP]) == 0)
					{
						IP = jumpAddr;
						DP = immedAddr;
					}
					SP--; break;
				}
				
#ifndef DISABLE_EVAL
			case  cEval:
				{
					CFunctionParser fpcopy(*this);
					double retVal = fpcopy.Eval(&Comp.Stack[SP-m_iVarAmount+1]);
					SP -= m_iVarAmount-1;
					Comp.Stack[SP] = retVal;
					break;
				}
#endif
				
			default:
				Comp.Stack[++SP]=Vars[Comp.ByteCode[IP]-VarBegin];
			}
		}
		
		return Comp.Stack[SP];
}

};